A kd-tree (short for k-dimensional tree) is a well-known space-partitioning data structure for organizing points in k-dimensional space. As an acceleration structure, kd-trees have been used in a variety of graphics applications.
Because of its significant usage in graphics, fast kd-tree construction has been a subject of much interest in recent years, with several CPU-based algorithms proposed and/or implemented. With a kd-tree, for example, scenes can be rendered, including by ray tracing to generate images by tracing light through pixels in a plane. Ray tracing is useful in commercial modeling and rendering software, but is computationally slow and thus not dynamically used to render frequently changing scenes.